package com.haidechizi.tree.balance;

public class AVL {

    Node root;

    public void addNode(Node node) {
        if (root == null) {
            root = node;
            return;
        }

        // 存在根节点
        root.addNode(node);
    }

    public void midShow() {
        if (root == null) {
            return;
        }
        this.root.midShow();
    }

    public Node searchNode(int value) {
        if (root == null) {
            return null;
        }
        return this.root.searchNode(value);
    }

    public void deleteNode(int i) {
        if (this.root == null) {
            return;
        }
        // 找到要删除的节点
        Node target = this.searchNode(i);
        if (target == null) {
            return;
        }
        // 找到要删除节点的父节点
        Node parent = searchParent(i);

        // 没有子节点
        if (target.left == null && target.right == null) {
            // 左子节点
            if (parent.value > target.value) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        } else if (target.left != null && target.right != null) {
            // 删除右子树的最小节点
            int min = deleteMin(target.right);
            // 用自小节点的值替换当前节点的值
            target.value = min;

            // 只有一个子节点
        } else {
            // 有左子节点
            if (target.left != null) {
                // target为左子节点
                if (parent.value > target.value) {
                    parent.left = target.left;
                } else {
                    parent.right = target.left;
                }
                // 有右子节点
            } else {
                // target为左子节点
                if (parent.value > target.value) {
                    parent.left = target.right;
                } else {
                    parent.right = target.right;
                }

            }

        }

    }

    private int deleteMin(Node right) {
        Node target = right;
        while (target.left != null) {
            target = target.left;
        }
        // 删除最小的节点
        deleteNode(target.value);
        return target.value;
    }

    public Node searchParent(int i) {
        if (this.root == null) {
            return null;
        }
        return this.root.searchParent(i);
    }
}
